class Solution {
private:
    unordered_map<int, int>m;
public:
    TreeNode* dfs(vector<int>& preorder, vector<int>inorder, int pl, int pr, int il, int ir) {
        if (pl > pr) {
            return NULL;
        }
        int proot = pl;
        int iroot = m[preorder[pl]];
        TreeNode* root = new TreeNode(preorder[pl]);
        int len = iroot - il;
        root->left = dfs(preorder, inorder, proot + 1, proot + len, il, iroot - 1);
        root->right = dfs(preorder, inorder, proot + len + 1, pr, iroot + 1, ir);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty()) { return NULL; }
        for (int i = 0; i < preorder.size(); i++) {
            m[inorder[i]] = i;
        }
        return dfs(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }
};